import java.util.PriorityQueue;

/**
 * @program: LeetCode
 * @description: LeetCode : 剑指 Offer II 076. 数组中的第 k 大的数字
 * @author: WXY
 * @create: 2023-01-01 14:56
 * @Version 1.0
 **/
public class Num_offer2_076_findKthLargest {
    public static int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int i = 0;
        for (; i < k; i++) {
            heap.offer(nums[i]);
        }
        for (int j = i; j < nums.length; j++) {
            heap.offer(nums[j]);
            heap.poll();
        }
        return heap.peek();
    }

    public static void main(String[] args) {
        int[] arr = {3, 2, 1, 5, 6, 4};
        int[] ans = build(arr, 2);
        printArry(ans);
        int kthLargest = findKthLargest1(arr, 2);
        System.out.println(kthLargest);
    }

    private static void printArry(int[] ans) {
        for (int n : ans) {
            System.out.print(n + " ");
        }
        System.out.println();
    }

    private static int[] build(int[] arr, int k) {
        int len = arr.length;
        MyMinHeap myMinHeap = new MyMinHeap(2);
        int i = 0;
        for (; i < k; i++) {
            myMinHeap.push(arr[i]);
        }
        for (int j = i; j < len; j++) {
            myMinHeap.pop();
            myMinHeap.push(arr[j]);
        }

        int[] ans = new int[len];
        int index = 0;
        while (!myMinHeap.isEmpty()) {
            ans[index++] = myMinHeap.pop();
        }
        return ans;
    }

    public static int findKthLargest1(int[] nums, int k) {
        MyMinHeap heap = new MyMinHeap(k);
        int i = 0;
        for (; i < k; i++) {
            heap.push(nums[i]);
        }
        for (int j = i; j < nums.length; j++) {
            heap.push(nums[j]);
            heap.pop();
        }
        return heap.peek();
    }

    public static class MyMinHeap {
        private final int limit;
        private int[] heap;
        private int heapSize;

        public MyMinHeap(int limit) {
            heap = new int[limit];
            this.limit = limit;
            this.heapSize = 0;
        }

        public boolean isEmpty() {
            return heapSize == 0;
        }

        public int length() {
            return heapSize;
        }

        public boolean isFull() {
            return heapSize == limit;
        }

        public void push(int value) {
            if (heapSize == limit) {
                return;
            }
            heap[heapSize] = value;
            heapInsert(heap, heapSize++);
        }

        public int pop() {
            int ans = heap[0];
            swap(heap, 0, --heapSize);
            heapify(heap, 0, heapSize);
            return ans;
        }

        public int peek() {
            return heap[0];
        }

        private void heapify(int[] arr, int index, int heapSize) {
            int left = index * 2 + 1;
            while (left < heapSize) {
                int small = left + 1 < heapSize && arr[left + 1] < arr[left] ? left + 1 : left;
                small = arr[small] < arr[index] ? small : index;
                if (small == index) break;
                swap(arr, small, index);
                index = small;
                left = left * 2 + 1;
            }
        }

        private void heapInsert(int[] arr, int index) {
            while (arr[index] < arr[(index - 1) / 2]) {
                swap(arr, index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }

        private void swap(int[] heap, int i, int j) {
            int tmp = heap[i];
            heap[i] = heap[j];
            heap[j] = tmp;
        }

    }
}
